class Solution {
    /*
        思路1（比较复杂）：
            朝着一个方向走，即for(int k=0; k<4; k++){}
            对于每个方法，一直走到底，即 while (check(tx,ty,n,m,matrix)){}
        
    */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int[][] nex = {{0,1},{1,0},{0,-1},{-1,0}};
        int n = matrix.length, m = matrix[0].length;
        int x = 0,y = 0;
        res.add(matrix[0][0]);
        while (res.size() < m*n){
            for(int k=0; k<4; k++){
                int tx = x + nex[k][0], ty = y + nex[k][1];
                while (check(tx,ty,n,m,matrix)){
                    res.add(matrix[tx][ty]);
                    matrix[x][y] = 999;
                    x = tx;
                    y = ty;
                    tx = x + nex[k][0];
                    ty = y + nex[k][1];
                }
            }
        }
        return res;
    }
    public boolean check(int x,int y,int n,int m,int[][] matrix){
        if(x<0 || x>=n || y<0 || y>=m)
            return false;
        if( matrix[x][y]<-100 || matrix[x][y]>100)
            return false;
        return true;
    }
}
class Solution {
    /*
        思路2（代码优化）：
            初始方向是向右，当路径超出界限或者进入之前访问过的位置时，
            顺时针旋转，进入下一个方向。
        即每碰一次壁，就顺时针换方向。
        这种方法的好处是不用套太多循环。
        
    */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int[][] nex = {{0,1},{1,0},{0,-1},{-1,0}};
        int n = matrix.length, m = matrix[0].length;
        int x = 0,y = 0, k = 0; // (x,y)表示当前所处的位置，k表示当前的行走方向
        for (int i = 1; i <= m*n; i++) {
            res.add(matrix[x][y]);
            matrix[x][y] = 999;
            int tx = x + nex[k][0], ty = y + nex[k][1];    // 每碰一次壁，行走方向就换一下
            if(tx<0 || tx>=n || ty<0 || ty>=m || matrix[tx][ty]<-100 || matrix[tx][ty]>100){
                k = (k+1)%4;
            }
            x = x + nex[k][0];
            y = y + nex[k][1];
        }
        return res;
    }
}